package 算法基础模板.chapter_04;

/**
 * 通过预处理逆元的方式求组合数
 * <p>
 * 首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
 * 如果取模的数是质数，可以用费马小定理求逆元
 * int qmi(int a, int k, int p)    // 快速幂模板
 * {
 * int res = 1;
 * while (k)
 * {
 * if (k & 1) res = (LL)res * a % p;
 * a = (LL)a * a % p;
 * k >>= 1;
 * }
 * return res;
 * }
 * <p>
 * // 预处理阶乘的余数和阶乘逆元的余数
 * fact[0] = infact[0] = 1;
 * for (int i = 1; i < N; i ++ )
 * {
 * fact[i] = (LL)fact[i - 1] * i % mod;
 * infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
 * }
 * <p>
 * 作者：yxc
 * 链接：https://www.acwing.com/blog/content/406/
 * 来源：AcWing
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author Summerday
 */
public class C2 {

    int N = 100010, mod = (int) (1e9 + 7);

    int[] fact = new int[N];
    int[] infact = new int[N];

    public static void main (String[] args) {

        C2 c2 = new C2();
        c2.init();

        System.out.println(c2.c(5, 2));

    }

    int qmi (int a, int k, int p) {
        int res = 1 % p;
        while (k > 0) {
            if ((k & 1) == 1) res = res * a % p;
            a = a * a % p;
            k >>= 1;
        }
        return res;
    }

    void init () {
        fact[0] = infact[0] = 1;
        for (int i = 1; i < N; i++) {
            fact[i] = fact[i - 1] * i % mod;
            infact[i] = qmi(i, mod - 2, mod) % mod;
        }
    }

    int c (int a, int b) {
        return fact[a] * infact[b] % mod * infact[a - b] % mod;
    }
}
